﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0210_RotatedDigits : IAlgorithm
    {
        // 788. 旋转数字 

        /*
        我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。
        如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。
        0, 1, 和 8 被旋转后仍然是它们自己；
        2 和 5 可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；
        6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。

        现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？

        提示：
            N 的取值范围是 [1, 10000]。
        */

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
        }

        // 算法
        static int[] check = { 0, 0, 1, -1, -1, 1, 1, -1, 0, 1 };
        int[,,] memo = new int[5, 2, 2];
        IList<int> digits = new List<int>();

        public int RotatedDigits(int n)
        {
            while (n != 0)
            {
                digits.Add(n % 10);
                n /= 10;
            }
            for (int i = 0, j = digits.Count - 1; i < j; ++i, --j)
                (digits[j], digits[i]) = (digits[i], digits[j]);

            for (int i = 0; i < 5; ++i)
                for (int j = 0; j < 2; ++j)
                    for (int k = 0; k < 2; ++k)
                        memo[i, j, k] = -1;

            int ans = DFS(0, 1, 0);
            return ans;
        }

        public int DFS(int pos, int bound, int diff)
        {
            if (pos == digits.Count) return diff;
            if (memo[pos, bound, diff] != -1) return memo[pos, bound, diff];

            int ret = 0;
            for (int i = 0; i <= (bound != 0 ? digits[pos] : 9); ++i)
                if (check[i] != -1)
                    ret += DFS(
                        pos + 1,
                        bound != 0 && i == digits[pos] ? 1 : 0,
                        diff != 0 || check[i] == 1 ? 1 : 0
                    );
            return memo[pos, bound, diff] = ret;
        }
    }
}
